The present invention generally relates to a real-time multiplier (high speed multiplier) for use in a digital signal processing system and, more particularly, to a real-time multiplier for multiplying 2's complement code numbers, instead of multiplying straight code data.
In general, a digital signal processing system does not always deal with positive values. For instance, considering a case that an A/D (analog to digital) converter converts an analog input data into a digital signal to obtain a new value by subtracting so-converted digital signals, when a subtraction of A-B is implemented, if the value A is bigger than the value B the output will be positive, where the output data is, of course, valid. However, if the value A is smaller than the value B the output data will be negative, an invalid value.
Therefore, it is understood that the digital code data must be able to deal with not only the positive value (number) but also the negative value. In practice, to meet this end the conventional digital signal processing system adopts various code systems.
To this end, a signed-magnitude code can be used, which has an extra bit for indicating whether the value of the code is positive or negative. This code system is divided into a part for indicating the absolute value of the code and another part for indicating the sign value thereof.
The so-called 2's complement code system can also be used. The basic principle of this 2's complement code is to use the concept of the complement numbers. Being consistently calculable both for addition and subtraction, this code system is widely used in general digital signal processing systems.
In a general digital signal processing system, the same result can be obtained regardless of the code system. When, however, a very high frequency (maybe, tens of MHz) is used for the operating clock, the various characteristics, particularly the speed characteristic of the digital signal processing system is strongly dependent upon the code system. According to the substantial digital signal processing system, the construction can be regarded as a combination of an adder, a subtractor, a multiplier and a divider, all of which is for processing correspondingly the input data code (for example, the straight code, the signed-magnitude code or the 2's complement code).
Of those operations of the adder, the subtractor, the multiplier and the divider presented above, the operations of the multiplier and the divider take a long time, comparatively. Therefore, the system speed is essentially dependent upon the construction of the multiplier and the divider.
It is well known that the 2's complement code system is advantageous in that the negative numbers can be easily expressed and operated so that the consistency for both the addition and subtraction can be used fruitfully in operating the numbers.
Referring to FIGS. 1A and 1B, the addition (X+Y) can be implemented by the circuit of FIG. 1A, while the subtraction (X-Y) by the circuit of FIG. 1B. It is accordingly noted that the difference between the above two circuits lies in the state of the carry input terminal Cin and an inverter 108 included only in the circuit of FIG. 1B. That is, when the carry input signal is 0 the circuit of FIG. 1A implements the addition and, however, when the carry signal is 1 the circuit of FIG. 1B implements the subtraction.
According to the general theory of the binary operation, all the bits of a binary number (addend) are added to the corresponding bits of a binary number to be added so as to perform the addition. However, for the subtraction of two binary numbers, all the bits of an addend are added to the corresponding bits of the 2's complement number of the binary number to be added. It should be noticed in advance that a 2's complement number can be obtained by adding 1 to the 1's complement of a number. This relation can be expressed as follows; EQU A-B=A+(-B)=A+B+1 (1)
The formula (1) can be embodied as an adder/subtractor shown in FIG. 2.
In the meantime, in the case where 2'S complement codes are multiplied, the 2'S complement codes are divided into a sign and an absolute value (magnitude of the code) and the absolute value is multiplied first and then the sign is corrected separately.
Considering only the magnitude of the code, it can be obtained by repeatedly implementing the 2's complement addition. However, if the multiplier and the multiplicand are the codes of a big number, then the system must be complicated to implement the addition. To settle this problem, a known apparatus for simplifying the hardware of the system is used in general, in which the apparatus calculates the partial sums by adding the two codes. Then the partial sums are added again to each other to obtain the multiplied result. When adapting such an apparatus, it is the most important drawback that the operation speed is considerably reduced.
There is disclosed another apparatus to speed up the operation, which introduces a pipeline-structured multiplier. In FIG. 3, a conventional magnitude multiplier having the pipeline structure is described. All latches in the drawing are synchronized with the system clock. The latch circuit 301 latches the input value Y of n-bit and the respective adders 310, 313, 317, 323 are all provided with the carry signal Cin of logic low state.
Thereafter, if the input value X of n-bit is latched in the latch circuit 302, the gates 303 and 304 performs the ANDing operation of the value X with the least significant bit (LSB) Y.sub.0 and the second LSB bit Y.sub.1, respectively. At the same moment, latch 306 latches the input value X. Then, output of the adder 310 is latched at the latch circuit 311 to be added to the output of the AND gate 308, at the adder 313. Thus, the latch output Sn of the latch circuit 316 becomes EQU Sn=X.multidot.Y.sub.0 +X.multidot.Y.sub.1 .multidot.2
Further, the partial sum Ps in this case is EQU Ps=X.multidot.Y.sub.0 +X.multidot.Y.sub.1 .multidot.2+X.multidot.Y.sub.2 .multidot.2.sup.2
In this way, the partial sums are obtained at each adder amd the result will be transferred to a next stage to be added to the multiplicand.
Such a magnitude multiplier employing the pipeline structure has indeed a strong point of speeding up the operation. It is, however, still disadvantageous in that this magnitude multiplier can not deal with the 2's complement.